# -*- coding: utf-8 -*-
#Importamos las librerias que vamos a utilizar a lo largo del trabajo
import random as r#Libreria para manejo de numeros aleatorios

#############################################
# Definimos la clase problema
class problema():
    def __init__(self, initial=None, goal=None):#Constructor de la clase problema
        #aqui se definiran los diferentes atributos que debe recibir al instanciarse el problema y que necesitaremos a lo largo del proceso
        #entre ellos pueden ser comportamientos especiales o conjuntos de datos que se cargan al principio
        self.initial= initial  or self.estado_random()# Puede recibir uno estado inicial o generar uno totalmetne aleatorio...
        self.goal= goal #En caso de que no se entregue un valor especifico deberemos definir la funcion goaltest.
        
    def successor(self, state): #Funcion encargada de generar los proximos sucesores
        #En esta funcion debemos definir a partir del estado a expandir, cuales son los sucesores del mismo
        #la forma en que debe retornarse la lista de sucesores es una lista formada por un conjunto de tuplas de dos elementos
        # sucesor[0]= string con el nombre de la accion aplicada
        # sucesor[1]= nuevo estado con la accion ya aplicada sobre el
        res= []
        return res
    
    def goal_test(self, state): #Funcion encargada de definir en la expancion si el estado actual es objetivo, devuelve un booleano referente al exito.
        #En caso de que no sea un estado especifico, deberiamos redefinir la funcion para testear si nuetro estado es meta.
        return (state == self.goal)

    def estado_random(self): #Funcion encargada de generar un estado valido totalmente al azar para iniciar nuestro problema...
        #Esta funcion debe definirse en los problemas que pueden instanciarse sin pasarles un estado inicial
        return None
    
    def path_cost(self,state): #Funcion encargada de definir el costo del camino
        return 1 #Como costo usaremos la plata que llevamos agregada, costo uniforme...

    def value(self, state): #Devuelve un valor de calidad para permitirle comprar entre dos estados...
        #Esta funcion es la encargada de devolver un valor numerico a partir del analisis de un estado especifico
        #Sera utilizada en algunos algoritmos para formar prioridades entre los nodos de la frontera a expandir.
        return 1



#############################################
# Definimos las clases nodo, a travez del cual se ira armando el conjunto de nodos posibles...
class nodo():
    def __init__(self, estado, padre=None, accion=None, costo_actual=0):
        self.estado= estado #Estado del problema en este nodo especifico
        self.padre= padre #Padre del nodo, antecesor del mismo
        self.accion=accion#Accion que transformo al antecesor en este nodo
        self.costo_actual= costo_actual#Costo desde el inicio hasta este nodo

    def camino(self): #Funcion encargada de calcular el camino desde este nodo hasta el inicio
        if self.padre: return [self.estado] + self.padre.camino()
        else: return [self.estado]

    def expandir(self,problema):#Funcion encargada de recibir un estado y un problema y devolver la lista de proximos nodos
        return [nodo(s[1],self,s[0],int(self.costo_actual)+problema.path_cost(s[1])) for s in problema.successor(self.estado)]#Genera lista instanciando nodos a partir de la lista devuelta por sucesores...


#############################################
# Empezamos a definir los metodos de busqueda
def colina(problema, comportamiento): #Recibe el problea instanciado y una funcion para elegir que tipo de ascension es.
    n= nodo(problema.initial)# Instanciamos el nodo actual para iniciar...
    frontera= [n]#Creamos la frontera inicial con el nodo base...
    while frontera: #Mientras la frontera no este vacia
        nuevo_nodo= comportamiento(frontera, problema)#Sacamos un nodo segun comportamiento de la frontera...
        if problema.goal_test(nuevo_nodo.estado): return nuevo_nodo.estado#Si llegamos a meta, devolvemos el estado meta...
        if problema.value(n.estado) > problema.value(nuevo_nodo.estado): return n.estado#Si es maximo local, lo retornamos y dejamos de buscar...
        frontera= nuevo_nodo.expandir(problema)#Expandimos el nodo nuevo
        n= nuevo_nodo#Lo guardamos como nodo actual para control de maximos locales...
    return None

#Diferentes comportamientos que modificaran el algoritmo colina inicial
control= lambda valor: int((int(valor<0)* -2) + 1)#Funcion que recibe un numero y se encarga de transformarlo en -1 0 1 dependiendo si es mayor o menor a 0 (para evitar numeros demaciado grandes)

def lista_ponderada(lista):#Recibi una lista ordenada por calidad de mayor a menor y devuelve lista aumentada probabilisticamente (al sacar un elemento aleatorio, los primeros tiene mas posibilidades)
    long_lista=5#Cuantas se ampliara la lista extendida
    rep_item=0.07#Cuantas veces se repetira cada elemento segun tamaño de lista
    decrecimiento=0.05#Cuanto ira decreciendo la repeticion de elementos por lista
    res= [] #Creamos la lista que devolvera ya preparada probabilisticamente
    elementos= len(lista) * long_lista #Crea el tamaño que tendra la nueva lista
    for item in lista: #Recorremos todos los elementos que posee la lista original ordenada
        res+= [item for c in range(1 + int(elementos * rep_item))]#generamos mini listas de este elemento, dando mas peso a los primeros
        elementos-= elementos * decrecimiento #cada mini lista que agregamos, hace la proxima sea mas pequeña-> prox item menos posibilidades
    return res #Los mejores (Primeros) elementos tienen mas posibilidades de salir, por que estan mas veces repetidos... (usar simplemente -> random.choice(res))

firstchoice= lambda frontera,problema: r.choice(frontera)#Primera eleccion (Elije uno al azar)
bestfirst= lambda frontera,problema: sorted(frontera, cmp=(lambda n1,n2: control(problema.value(n2.estado) - problema.value(n1.estado))))[0]#Primero el mejor (Ordena por value() y saca el primero)
estocastic= lambda frontera,problema: r.choice(lista_ponderada(sorted(frontera,cmp=(lambda n1,n2: control(problema.value(n2.estado) - problema.value(n1.estado))))))#Estocastica, segun valuacion definida en el problema...
